package org.example.myleet.sort;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.Utils.ListNode;
import org.example.myleet.Utils.Parser;

import java.util.*;
import java.util.stream.Collectors;

public class SortSolution {

    //剑指Offer114
    public String alienOrder(String[] words) {
        //smaller -> bigger，记录入度，这里的入度指从字典序更小的字母指向字典序更大的字母，记作字典序更大的字母入度+1
        //例如例子中字典序w<e的情况下，++in['e'-'a'];
        int[] in = new int[26];
        //记录所有出现过的字符，用于比较最终结果是否得到合法的字典序结果
        Set<Character> allChars = new HashSet<>(26);
        //记录smaller -> biggerSet，即通过分析words之后，得到字典序更小的字母对应的字典序比它大的字母集合
        HashMap<Character, Set<Character>> charMapBiggerChars = new HashMap<>();
        //分析words里面的有效的字典序配对
        for (int i = 0; i < words.length; ++i) {
            String w1 = words[i];
            for (int j = i + 1; j < words.length; ++j) {
                String w2 = words[j];
                int minLen = Math.min(w1.length(), w2.length());
                Character smaller = null;
                Character bigger = null;
                for (int k = 0; k < minLen; ++k) {
                    char c1 = w1.charAt(k);
                    char c2 = w2.charAt(k);
                    if (c1 == c2) {
                        //字母相同，比较下一个
                        continue;
                    }
                    //找到一对字典序结果
                    smaller = c1;
                    bigger = c2;
                    break;
                }
                if (smaller != null) {
                    //找到一对字典序结果
                    Set<Character> biggerSet = charMapBiggerChars.getOrDefault(smaller, new HashSet<>());
                    if (!biggerSet.contains(bigger)) {
                        biggerSet.add(bigger);
                        charMapBiggerChars.put(smaller, biggerSet);
                        //是新出现的字典序配对，记录入度
                        ++in[bigger - 'a'];
                    }
                } else if (w1.length() > w2.length()) {
                    //这里讨论一种很不合理的排序方式，例如["abc","ab"]
                    //在找不到一对字典序结果的情况下更长的单词排在更短的单词前面，这种一定找不到合理的字母顺序
                    return "";
                }
            }
            for (char c : w1.toCharArray()) {
                //记录所有出现过的字母
                allChars.add(c);
                if (!charMapBiggerChars.containsKey(c)) {
                    //如果其中有些字母没有出现在字典序配对中，则按没有比它字典序更大的字母记录下来，不增加入度
                    charMapBiggerChars.put(c, new HashSet<>());
                }
            }
        }
        //下面是拓扑排序，即按入度从小到大排序，做法为：
        //1、初始化找到入度为0的节点，标记为待查看节点
        //2、访问待查看节点，加入到结果中，找到他们的子节点，然后去掉这条边，此时对应节点的入度-1
        //3、如果存在节点的入度变成0，则此节点又可以标记为待查看节点，重复步骤2
        //4、直到没有节点标记为待查看节点，此时完成拓扑排序
        //遍历找到所有入度为0的节点，入队列，即标记为待查看节点
        Deque<Character> deque = new LinkedList<>();
        for (char c = 'a'; c <= 'z'; ++c) {
            if (charMapBiggerChars.containsKey(c)) {
                if (in[c - 'a'] == 0) {
                    deque.offer(c);
                }
            }
        }
        //字母字典序结果
        List<Character> result = new ArrayList<>(26);
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; ++i) {
                //访问待查看节点
                Character c = deque.poll();
                //接入到排序结果中
                result.add(c);
                //子节点，逐个去掉1入度
                Set<Character> biggerSet = charMapBiggerChars.remove(c);
                if (Objects.nonNull(biggerSet)) {
                    for (Character b : biggerSet) {
                        --in[b - 'a'];
                        if (in[b - 'a'] == 0) {
                            //入度降为0的节点再标记成待查看节点
                            deque.offer(b);
                        }
                    }
                }
            }
        }
        if (result.size() < allChars.size()) {
            //如果存在有些字母字典序之间成环，则不能得出一个合法的字母字典序结果
            return "";
        }
        return result.stream().map(Object::toString).collect(Collectors.joining(""));
    }

    //面试题 17.14. 最小K个数
    public int[] smallestK(int[] arr, int k) {
        randomizedSelected(arr, 0, arr.length - 1, k);
        int[] vec = new int[k];
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }
    private void randomizedSelected(int[] arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int pos = randomizedPartition(arr, l, r);
        int num = pos - l + 1;
        if (k == num) {
            return;
        } else if (k < num) {
            randomizedSelected(arr, l, pos - 1, k);
        } else {
            randomizedSelected(arr, pos + 1, r, k - num);
        }
    }
    // 基于随机的划分
    private int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l;
        swap(nums, r, i);
        return partition(nums, l, r);
    }
    private int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    //p56. 合并区间
    public int[][] merge(int[][] intervals) {
        //先对所有区间排序，每个区间第一个数字按升序排列
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        List<int[]> result = new ArrayList<>();
        //第i个区间
        int i = 0, len = intervals.length;
        //新区间的左右位置
        int left, right;
        while (i < len) {
            left = intervals[i][0];
            right = intervals[i][1];
            while (i < (len-1) && right >= intervals[i+1][0]) {
                //i不是最后一个，即还有i+1的情况时，考虑新区间右端是否比下一个区间的左端大或相等，如果right及至下一个区间左端，融合这个区间
                right = Math.max(right, intervals[i+1][1]);
                ++i;
            }
            //获得一个新区间，加入结果中
            result.add(new int[]{left, right});
            ++i;
        }
        int[][] answer = new int[result.size()][2];
        for (int k=0; k<result.size(); k++) {
            answer[k] = result.get(k);
        }
        return answer;
    }

    //p57. 插入区间
    public int[][] insert(int[][] intervals, int[] newInterval) {
        //先做一个新的数组把新的区间加入进来
        int[][] newIntervals = new int[intervals.length+1][2];
        int i;
        for (i=0; i<intervals.length; i++) {
            newIntervals[i] = intervals[i];
        }
        newIntervals[i] = newInterval;
        //然后就跟p56一样解决就行
        //先对所有区间排序，每个区间第一个数字按升序排列
        Arrays.sort(newIntervals, Comparator.comparingInt(o -> o[0]));
        List<int[]> result = new ArrayList<>();
        //第i个区间
        i = 0;
        int len = newIntervals.length;
        //新区间的左右位置
        int left, right;
        while (i < len) {
            left = newIntervals[i][0];
            right = newIntervals[i][1];
            while (i < (len-1) && right >= newIntervals[i+1][0]) {
                //i不是最后一个，即还有i+1的情况时，考虑新区间右端是否比下一个区间的左端大或相等，如果right及至下一个区间左端，融合这个区间
                right = Math.max(right, newIntervals[i+1][1]);
                ++i;
            }
            //获得一个新区间，加入结果中
            result.add(new int[]{left, right});
            ++i;
        }
        int[][] answer = new int[result.size()][2];
        for (int k=0; k<result.size(); k++) {
            answer[k] = result.get(k);
        }
        return answer;
    }

    /**
     * 148【归并排序】排序链表
     * 参考：Sort List——经典（链表中的归并排序） https://www.cnblogs.com/qiaozhoulin/p/4585401.html
     *
     * 归并排序法：在动手之前一直觉得空间复杂度为常量不太可能，因为原来使用归并时，都是 O(N)的，
     * 需要复制出相等的空间来进行赋值归并。对于链表，实际上是可以实现常数空间占用的（链表的归并
     * 排序不需要额外的空间）。利用归并的思想，递归地将当前链表分为两段，然后merge，分两段的方
     * 法是使用 fast-slow 法，用两个指针，一个每次走两步，一个走一步，直到快的走到了末尾，然后
     * 慢的所在位置就是中间位置，这样就分成了两段。merge时，把两段头部节点值比较，用一个 p 指向
     * 较小的，且记录第一个节点，然后 两段的头一步一步向后走，p也一直向后走，总是指向较小节点，
     * 直至其中一个头为NULL，处理剩下的元素。最后返回记录的头即可。
     *
     * 主要考察3个知识点，
     * 知识点1：归并排序的整体思想
     * 知识点2：找到一个链表的中间节点的方法
     * 知识点3：合并两个已排好序的链表为一个新的有序链表
     */
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        return mergeSort(head);
    }
    private ListNode mergeSort(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        //双指针法找出中间点做分割，慢指针每次走一步，快指针每次走两步，快指针到头时，慢指针作为分割点
        //slowPre是个巧妙到设计，表示慢指针的上一个节点，用来给左边部分收尾
        ListNode fastP = head, slowP = head, slowPre = null;
        while (fastP != null && fastP.next != null) {
            fastP = fastP.next.next;
            slowPre = slowP;
            slowP = slowP.next;
        }
        //左边部分收尾，形成l->@->@..->@->null，r->@->@..->@->null，这样两部分
        slowPre.next = null;
        //然后是递归处理左右分割的各部分
        ListNode l = mergeSort(head);
        ListNode r = mergeSort(slowP);
        return merge(l ,r);
    }
    private ListNode merge(ListNode l, ListNode r) {
        //临时结果链表
        ListNode dummyHead = new ListNode(Integer.MIN_VALUE), h = dummyHead;
        //遍历左边的链表和右边的链表
        ListNode lp = l, rp = r;
        while (lp != null || rp != null) {
            if (lp != null && rp != null) {
                //比较两边链表的当前节点的大小，取小的安放到临时结果链表的末尾
                if (lp.val < rp.val) {
                    h.next = lp;
                    lp = lp.next;
                } else {
                    h.next = rp;
                    rp = rp.next;
                }
            } else if (lp != null) {
                h.next = lp;
                lp = lp.next;
            } else {
                h.next = rp;
                rp = rp.next;
            }
            h = h.next;
        }
        //临时结果链表的next就是融合完后的结果
        return dummyHead.next;
    }

    /**
     * 164【桶排序】最大间距
     * 问题关键：请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
     * 使用桶排序的思想对数据的间距作区间划分
     * 参考：https://blog.csdn.net/zxzxzx0119/article/details/82889998
     * 思路:
     * 先找到数组的最大值和最小值，记为max和min；
     * 假设数组长度为N，准备N+1个桶，把max放在N+1号桶，nums中在[min,max)范围上的数放在1~N号桶中，对于1 ~ N号桶的每一个桶来说，负责的区间大小为(max - min )/N；
     * 注意每个桶中存的不是很多的数，只存三个值，是否有数进入过这个桶，以及所有进入这个桶的数的最大值、最小值；
     * 最后计算相邻非空桶的间距(当前桶的min 减去前一个桶的max) ，然后记录更新最大值；
     */
    public int maximumGap(int[] nums) {
        if (2 > nums.length) {
            return 0;
        }
        int max = nums[0], min = nums[0], len = nums.length;
        //一次O(n)
        for (int i = 1; i < len; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        if (min == max) {
            return 0;
        }
        //3位代表意思是：有数字在此区域(>1)，最大数字，最小数字
        //空间复杂度O(3n)，线性空间复杂度
        int[][] buckets = new int[len + 1][3];
        int idx;
        //两次O(n)
        for (int i = 0; i < len; i++) {
            //通过一个公式计算将nums[i]映射到某个桶id上
            idx = (int) (((long) nums[i] - (long) min) * (long) len / ((long) max - (long) min));
            if (buckets[idx][0] < 1) {
                buckets[idx][0] = 1;
                buckets[idx][1] = nums[i];
                buckets[idx][2] = nums[i];
            } else {
                buckets[idx][1] = Math.max(buckets[idx][1], nums[i]);
                buckets[idx][2] = Math.min(buckets[idx][2], nums[i]);
            }
        }
        //遍历非空桶的相邻桶获得最大间距
        int maxInterval = 0;
        int preIdx = 0;
        //三次O(n)，总复杂度O(3n)，线性时间复杂度
        for (int i = 1; i < len + 1; i++) {
            if (buckets[i][0] > 0) {
                maxInterval = Math.max(maxInterval, buckets[i][2] - buckets[preIdx][1]);
                preIdx = i;
            }
        }
        return maxInterval;
    }

    /**
     * 179【贪心+排序】最大数
     * 6 ms
     * 对于"34323"和"3432"的比较，相当于两个"3432"拼在一起，多出来的3在拼接后将位于后一个"3432"的前面或后面
     * 由于'3'比第二位的4更小，因此'3'应该位于"3432"的后面，因此结果应为["3432","34323"]这样的排序
     * 关于数字特殊排序的题目，定义好数字排在前面的规则：
     * 1、考虑长度相的部分，按顺序比较相同位置的字符，字符更大的排在前面
     * 2、对于较长的字符串多出来的部分，考虑这部分是放在相同部分的前面还是后面，即多出来的字符串与短的字符串比较，比短字符串更大的应该排在前面
     * 需要注意的地方：当输入全部为0时，需要对开头的0做去除
     */
    public String largestNumber(int[] nums) {
        ArrayList<String> numbers = new ArrayList<>(nums.length);
        for (int num : nums) {
            numbers.add(Integer.toString(num));
        }
        numbers.sort(this::customCompare179);
        StringBuilder sb = new StringBuilder();
        for (String number : numbers) {
            sb.append(number);
        }
        //去除数字开头多余的0
        int start = 0;
        while (start < sb.length() - 1 && '0' == sb.charAt(start)) {
            ++start;
        }
        return sb.substring(start, sb.length());
    }
    private int customCompare179(String num1, String num2) {
        int smallerSize = Math.min(num1.length(), num2.length());
        //比较长度相同的部分
        for (int i = 0; i < smallerSize; ++i) {
            char c1 = num1.charAt(i), c2 = num2.charAt(i);
            if (c2 < c1) {
                return -1;
            }
            if (c2 > c1) {
                return 1;
            }
        }
        //num1更长情况下的比较
        if (smallerSize < num1.length()) {
            for (int i = smallerSize; i < num1.length(); ++i) {
                char c1 = num1.charAt(i);
                for (int j = 0; j < num2.length(); ++j) {
                    char c2 = num2.charAt(j);
                    if (c1 < c2) {
                        return 1;
                    }
                    if (c1 > c2) {
                        return -1;
                    }
                }
            }
        }
        //num2更长情况下的比较
        if (smallerSize < num2.length()) {
            for (int i = smallerSize; i < num2.length(); ++i) {
                char c2 = num2.charAt(i);
                for (int j = 0; j < num1.length(); ++j) {
                    char c1 = num1.charAt(j);
                    if (c1 < c2) {
                        return 1;
                    }
                    if (c1 > c2) {
                        return -1;
                    }
                }
            }
        }
        return 0;
    }

    /**
     * 274【排序】H指数
     */
    public int hIndex(int[] citations) {
        int N = citations.length;
        Arrays.sort(citations);
        if (citations[N - 1] == 0) {
            return 0;
        }
        if (N == 1) {
            return 1;
        }
        int H = 0;
        for (int h = 1; h <= N; ++h) {
            int positive = N - h;
            if (citations[positive] >= h) {
                if (positive == 0) {
                    H = h;
                } else {
                    int negative = positive - 1;
                    if (citations[negative] <= h) {
                        H = h;
                    }
                }
            } else {
                break;
            }
        }
        return H;
    }

    /**
     * 1333【排序】餐厅过滤器
     */
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        List<int[]> validRes = new ArrayList<>(restaurants.length);
        for (int[] res : restaurants) {
            if (veganFriendly == 1 && res[2] == 0) {
                continue;
            }
            if (res[3] > maxPrice || res[4] > maxDistance) {
                continue;
            }
            validRes.add(new int[]{res[0], res[1]});
        }
        validRes.sort((a, b) -> {
            if (a[1] == b[1]) {
                return b[0] - a[0];
            }
            return b[1] - a[1];
        });
        List<Integer> answer = new ArrayList<>(validRes.size());
        for (int[] res : validRes) {
            answer.add(res[0]);
        }
        return answer;
    }

    //p1630
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        int m = l.length;
        List<Boolean> answer = new ArrayList<>(m);
        for (int i = 0; i < m; ++i) {
            int len = r[i] - l[i] + 1;
            int max = nums[l[i]], min = nums[l[i]];
            for (int j = l[i] + 1; j <= r[i]; ++j) {
                max = Math.max(max, nums[j]);
                min = Math.min(min, nums[j]);
            }
            if ((max - min) % (len - 1) != 0) {
                answer.add(false);
                continue;
            }
            boolean b = true;
            int d = (max - min) / (len - 1);
            if (d == 0) {
                for (int j = l[i]; j <= r[i]; ++j) {
                    if (nums[j] != min) {
                        b = false;
                        break;
                    }
                }
            } else {
                boolean[] visited = new boolean[len];
                for (int j = l[i]; j <= r[i]; ++j) {
                    if ((nums[j] - min) % d != 0) {
                        b = false;
                        break;
                    }
                    int t = (nums[j] - min) / d;
                    visited[t] = true;
                }
                for (int j = 0; j < visited.length; ++j) {
                    if (!visited[j]) {
                        b = false;
                        break;
                    }
                }
            }
            answer.add(b);
        }
        return answer;
    }

    //p1893
    public boolean isCovered(int[][] ranges, int left, int right) {
        Arrays.sort(ranges, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        LinkedList<int[]> mergedRanges = new LinkedList<>();
        mergedRanges.add(ranges[0]);
        for (int i = 1; i < ranges.length; ++i) {
            int[] lastMergedRange = mergedRanges.peekLast();
            if (lastMergedRange[1] >= ranges[i][0] - 1) {
                if (lastMergedRange[1] < ranges[i][1]) {
                    mergedRanges.pollLast();
                    lastMergedRange[1] = ranges[i][1];
                    mergedRanges.offerLast(lastMergedRange);
                }
            } else {
                mergedRanges.add(ranges[i]);
            }
        }
        for (int[] mergedRange : mergedRanges) {
            if (mergedRange[0] <= left && right <= mergedRange[1]) {
                return true;
            }
        }
        return false;
    }

    /**
     * 2300【桶排序+二分查找】咒语和药水的成功对数
     * 桶排序实测比快速排序快一点点大概8ms左右，28ms→20ms
     */
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length, m = potions.length;
        //先对potions进行桶排序，先找出最大值，确定需要建桶的数量
        int mx = 0;
        for (int j = 0; j < m; ++j) {
            mx = Math.max(mx, potions[j]);
        }
        int[] buckets = new int[mx + 1];
        //建桶后将每个potion放到对应桶中
        for (int potion : potions) {
            buckets[potion]++;
        }
        //从桶中按顺序还原potion
        int j = 0;
        for (int x = 1; x <= mx; ++x) {
            while (buckets[x] > 0) {
                potions[j++] = x;
                buckets[x]--;
            }
        }
        //下面利用二分查找寻找题目要求的答案
        int[] answer = new int[n];
        for (int i = 0; i < n; ++i) {
            int l = 0, r = m - 1, spell = spells[i];
            while (l < r) {
                int mid = (l + r) >> 1;
                if ((long) spell * potions[mid] >= success) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if ((long) spell * potions[l] >= success) answer[i] = m - l;
        }
        return answer;
    }

    //p2347
    public String bestHand(int[] ranks, char[] suits) {
        boolean flush = true;
        for (int i = 1; i < 5; ++i) {
            if (suits[i] != suits[0]) {
                flush = false;
                break;
            }
        }
        if (flush) return "Flush";
        Arrays.sort(ranks);
        int l = 0, r = 1, m = 1;
        while (true) {
            m = Math.max(m, r - l);
            if (r >= 5) {
                break;
            }
            if (ranks[r] == ranks[l]) {
                ++r;
            } else {
                ++l;
                r = l + 1;
            }
        }
        switch (m) {
            case 5:
            case 4:
            case 3: return "Three of a Kind";
            case 2: return "Pair";
            default: return "High Card";
        }
    }

    //p2357
    public int minimumOperations(int[] nums) {
        Arrays.sort(nums);
        int op = 0, prev = 0;
        for (int num : nums) {
            if (prev < num) {
                prev = num;
                ++op;
            }
        }
        return op;
    }

    //p2418
    public String[] sortPeople(String[] names, int[] heights) {
        int n = heights.length;
        quickSort2418(names, heights, 0, n - 1);
        return names;
    }
    private void quickSort2418(String[] names, int[] heights, int start, int end) {
        if (end - start <= 0) {
            return;
        }
        if (end - start == 1) {
            if (heights[start] < heights[end]) {
                String ts = names[start];
                names[start] = names[end];
                names[end] = ts;
                int t = heights[start];
                heights[start] = heights[end];
                heights[end] = t;
            }
            return;
        }
        int pivot = heights[start];
        int i = start, j = end;
        while (i < j) {
            while (heights[j] < pivot) {
                --j;
            }
            String ts = names[i];
            names[i] = names[j];
            names[j] = ts;
            int t = heights[i];
            heights[i] = heights[j];
            heights[j] = t;
            while (heights[i] > pivot) {
                ++i;
            }
            ts = names[i];
            names[i] = names[j];
            names[j] = ts;
            t = heights[i];
            heights[i] = heights[j];
            heights[j] = t;
        }
        quickSort2418(names, heights, start, j);
        quickSort2418(names, heights, j + 1, end);
    }

    public static void main(String[] args) {
        SortSolution solution = new SortSolution();

//        Assert.isTrue(solution.isCovered(Parser.parse("[[25,42],[7,14],[2,32],[25,28],[39,49],[1,50],[29,45],[18,47]]"), 15, 38));
//        Assert.isTrue(solution.isCovered(Parser.parse("[[1,2],[3,4],[5,6]]"), 2, 5));
//        Assert.isTrue(!solution.isCovered(Parser.parse("[[1,10],[10,20]]"), 21, 21));
//
//        Assert.isTrue("Three of a Kind".equals(solution.bestHand(new int[]{4,4,2,4,4}, new char[]{'d','a','a','b','c'})));
//        Assert.isTrue("Pair".equals(solution.bestHand(new int[]{2,5,10,10,7}, new char[]{'b','b','a','b','c'})));
//
//        Assert.isTrue("[true,false,true]".equals(JsonUtils.toJson(solution.checkArithmeticSubarrays(new int[]{4,6,5,9,3,7}, new int[]{0,0,2}, new int[]{2,3,5}))));

        Assert.isTrue("[\"EPCFFt\",\"RPJOFYZUBFSIYp\",\"VOYGWWNCf\",\"Vk\",\"Sgizfdfrims\",\"IEO\",\"QTASHKQ\",\"WSpmqvb\"]".equals(JsonUtils.toJson(solution.sortPeople(new String[]{"IEO","Sgizfdfrims","QTASHKQ","Vk","RPJOFYZUBFSIYp","EPCFFt","VOYGWWNCf","WSpmqvb"}, new int[]{17233,32521,14087,42738,46669,65662,43204,8224}))));
        Assert.isTrue("[\"Mary\",\"Emma\",\"John\"]".equals(JsonUtils.toJson(solution.sortPeople(new String[]{"Mary","John","Emma"}, new int[]{180,165,170}))));
    }
}
